1. Field of the Invention
The present invention relates to data processing systems and methods and more particularly to systems and methods for designing data processing systems having reduced power dissipation characteristics.
2. Prior Art
Assigning binary codes to the symbolic state values of a finite state machine (FSM) is a very complex problem. For small machines, algorithms based on Boolean algebra or exact methods may be applied. (See for example, Devadas, et al., "Exact Algorithms for Output Encoding, State Assignment and Four-Level Boolean Minimization," IEEE Transaction on Computer-Aided Design of Integrated Circuit Systems, Vol. 10, No. 1, pp 13-27, January 1991.) Various heuristic techniques are required for larger designs. (See for example, De Micheli, et al., "Optimal State Assignment for Finite State Machines," IEEE Transactions on Computer-Aided Design, Vol. CAD-4, pp. 269-284, July 1985; De Micheli, "Symbolic Design of Combinational and Sequential Logic Circuits Implemented by Two-level Logic Macros," IEEE Transactions on Computer-Aided Design, Vol. CAD-5, pp. 597-616, October 1986; Amann, et al., "Optimal State Chains and State Codes in Finite State Machines," IEEE Transactions on Computer-Aided Design, Vol. 8, No. 2, February 1989; Devadas, et al., "Mustang: State Assignment of Finite State Machines for Optimal Multi-level Logic Implementations," IEEE Transactions on Computer-Aided Design, Vol. 7, December 1988; and Lin, et al., "Synthesis of Multiple Level Logic from Symbolic High-level Description Languages," VLSI, 1989.) The primary goal of these techniques is to reduce the amount of area required, and it has been shown that careful assignment of state codes can make a significant difference in total area.
As designs become larger, a new concern appears. Even if the design fits on the chip area allocated, if it dissipates too much power, then limitations may be placed on performance or thermal operating environment. Furthermore, for battery powered applications, such as, laptop computers, the additional current drain means a shorter operating time. If the target technology is CMOS, then power dissipation can be controlled by limiting the number of switching transitions in the design, since power dissipation is directly proportional to the number of switching transitions.
Although the above references generally discuss optimizing state assignments in finite state machines for the purpose of reducing chip area, none of the references teach nor suggest a state assignment technique which employs state transition probabilities to reduce power dissipated by the integrated circuit chip.
An article by Roy, et al. entitled "Syclop: Synthesis of CMOS Logic for Low Power Applications," published in the IEEE Transactions, 1992, presents a system which synthesizes finite state machines and combinatorial logic for low power applications. The system described in the paper minimizes the area and the transition density at the internal nodes of a CMOS circuit. The minimization is based on assumed input signal probabilities and transition densities. The authors presume a signal probability of 0.5 and a transition density of 0.5 for all cases.
The article relates to multi-level logic and uses assumed signal probabilities and transition densities wherein the system in accordance with the present invention uses measured transition probabilities. Further, the system taught by the article uses simulated annealing whereas the system and method according the present invention uses state chains. Although the system taught by the article is very sensitive to changes in transition probabilities, the system and method according to the present invention was specifically developed with state chains to minimize sensitivity to transition probability changes.
Another article by Roy, et al. entitled "Circuit Activity Based Logic Synthesis for Low Power Reliable Operations," was published in IEEE Transactions, December 1993, at pp. 503-513, inclusive. This article recognizes that the average number of transitions at a node is a measure of power dissipation in digital CMOS circuits. The paper addresses the problem of finite state machines and combinational logic synthesis to minimize the average number of transitions at CMOS circuit nodes for battery operated low power operations and increased reliability, while minimizing area at the same time. Logic can be optimally synthesized suited for different applications requiring different types of inputs.
Although the paper refers to circuit simulation and transition density simulation, all examples in the paper employ a presumed signal probability of 0.5 and a transition density of 0.5. The paper does not teach nor suggest a system for designing a finite state machine to achieve minimum power dissipation as is taught and claimed in accordance with the present invention.
A paper by Yang, et al. entitled "On the Relationship Between Input Encoding and Logic Minimization," published at the 23rd Annual Hawaii International Conference on System Sciences, Vol. 1, pp. 377-386, 1990, discusses a theoretical formulation of input encoding based on a concept of compatibility of dichotomies. The paper proposes the extraction of essential prime dichotomies which serve the same purpose of the extraction of essential prime implicants in logic minimization. The paper provides a method which can be applied to the input encoding of combinational logic in the state assignment of finite state machines in both two level and multi-level implementations.
However, the paper does not each a technique for reducing power dissipation in a logic system by reducing switching activity as does the present invention.
A paper by Du, et al. entitled "Muse: A Multi-Level Symbolic Encoding Algorithm for State Assignment," published in the proceedings of the 23rd Annual Hawaii International Conference on System Sciences, pp. 367-376, 1990, presents a state assignment algorithm for encoding of finite state machines targeted for multi-level implementation. The computation of weights of state pairs is based on a multi-level present representation of the one-hot encoded state machine.
The paper does not teach a system and method for reducing power dissipation in a logic system.